1. Field of the Invention
The present invention relates to compilers for computer systems. More specifically, the present invention relates to a method and an apparatus for creating multiple versions of loops to facilitate modulo scheduling.
2. Related Art
The latest generation of processors are able to execute multiple instructions simultaneously. However, compilers need to arrange executable code to take advantage of this parallel processing capability. Modulo scheduling is one such way in which compilers can arrange code to perform as many instructions as possible in each clock cycle.
Many computationally intensive applications spend the bulk of their time executing loops. Modulo scheduling extracts instruction-level parallelism in loops, and can thereby significantly increase the execution speed of a program. Hence, in order to maximize system performance, it is important that a compiler be able to modulo schedule as many loops as possible.
There are many different types of loops, and it may not be possible to modulo schedule all of them. In order to modulo schedule a loop, it is important that the loop be in a form such that the number of iterations of the loop be determined before the loop is executed. If the loop has a termination condition that is based on a “not-equal-to” test, then it may not be possible to determine the trip count of the loop because the loop might be an infinite loop.
In order to modulo schedule the loop, the loop has to be transformed into a form which allows the trip count of the loop to be determined before the loop is executed. Note that if the loop counter gets incremented or decremented by one, then the loop can be trivially transformed into a loop with a less than or greater than test.
What is needed is a method and apparatus for transforming loops that cannot be modulo scheduled, such as loops with a “not-equal-to” test, into a form that allows them to be modulo scheduled.